class FreqStack
{
public:
    FreqStack()
    {
    }

    void push(int val)
    {
        ++numFreq[val];
        freqStack[numFreq[val]].push(val);
    }

    int pop()
    {
        while (true)
        {
            auto &[firstFreq, s] = *freqStack.begin();
            if (s.empty())
            {
                freqStack.erase(firstFreq);
                continue;
            }
            int val = s.top();
            s.pop();
            if (firstFreq == numFreq[val])
            {
                --numFreq[val];
                return val;
            }
        }
        return -1;
    }

private:
    unordered_map<int, int> numFreq;
    map<int, stack<int>, greater<int>> freqStack;
};

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack* obj = new FreqStack();
 * obj->push(val);
 * int param_2 = obj->pop();
 */